home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / source / src / dict / _ab_tree.c next >
Encoding:
C/C++ Source or Header  |  1994-11-16  |  33.0 KB  |  1,272 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  _ab_tree.c
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. #include <LEDA/impl/ab_tree.h>
  17.  
  18. //---------------------------------------------------------------
  19. //  
  20. //  Michael Wenzel:
  21. //  function insert_at_item added
  22. //
  23. //  double links between leaf and inner node with same key
  24. //
  25. //  delete overwrites copies of keys in inner nodes
  26. //
  27. //  leafs are nodes of degree 1, linked by son[1], son[2]
  28. //
  29. //---------------------------------------------------------------
  30.  
  31. //------------------------------------------------------------------
  32. // constructors
  33. //------------------------------------------------------------------
  34.  
  35.  
  36. ab_tree_node::ab_tree_node(int p_,int height_,int index_,ab_tree_node* father_,int b)
  37. {
  38.     son  = (ab_tree_node**) allocate_words(b+2);   /* array[1..b+1] */
  39.     k    = (GenPtr*) allocate_words(b+1);             /* array[1..b]   */
  40.     same = (ab_tree_node**) allocate_words(b+1);   /* array[1..b]   */
  41.  
  42.  
  43.     // position 0 contains the size of the array:
  44.  
  45.     son[0]  = (ab_tree_node*)(b+2);
  46.     k[0]    = GenPtr(b+1);
  47.     same[0] = (ab_tree_node*)(b+1);
  48.  
  49.     p=p_;
  50.     height=height_;
  51.     index=index_;
  52.     father=father_;
  53.     for(int i=1;i<=(b+1);son[i++]=0);
  54.     for(i=1;i<=b;k[i++]=0);
  55.     for(i=1;i<=b;same[i++]=0);                
  56.    }
  57.  
  58.  
  59.  ab_tree_node::~ab_tree_node() 
  60.   { deallocate_words(son,int(son[0]));    /* first array element gives size */
  61.     deallocate_words(same,int(same[0]));
  62.     deallocate_words(k,int(k[0]));
  63.    }
  64.  
  65.  
  66.  
  67.  
  68.  ab_tree::ab_tree(int a_,int b_)
  69.  {
  70.    root=maximum=minimum=0;
  71.    count=0;
  72.    height=-1;
  73.    if((a_>=2)&&(b_>=2*a_-1))
  74.     { a=a_;
  75.       b=b_;
  76.      }
  77.    else error_handler(1,"ab_tree: illegal arguments (a,b) in tree constructor");
  78.  }
  79.  
  80.  ab_tree::ab_tree(const ab_tree& T)
  81.   {
  82.      if (T.root==0) {root=maximum=minimum=0;height=-1;count=0;}
  83.      else { abnode help=0;
  84.         root = T.copy_ab_tree(T.root,help,T.b);
  85.             maximum=help;
  86.             help=root;
  87.             while (help->p) help=help->son[1];
  88.         minimum=help;
  89.             height=T.height;
  90.             count=T.count;
  91.           };
  92.      a=T.a;
  93.      b=T.b;
  94.   }
  95.  
  96. //-----------------------------------------------------------------
  97. // operators
  98. //-----------------------------------------------------------------
  99.  
  100.  ab_tree& ab_tree::operator=(const ab_tree& T)
  101.   {  if (this == &T) return *this;
  102.  
  103.      clear();
  104.  
  105.      if (T.root!=0) 
  106.      { abnode help=0;
  107.        root=copy_ab_tree(T.root,help,T.b);
  108.        maximum=help;
  109.        help=root;
  110.        while (help->p) help=help->son[1];
  111.        minimum=help;
  112.        height=T.height;
  113.        count=T.count;
  114.       };
  115.  
  116.      a=T.a;
  117.      b=T.b;
  118.  
  119.      return *this;
  120.   }
  121.  
  122.  
  123. //-----------------------------------------------------------------
  124. // member functions
  125. //-----------------------------------------------------------------
  126.  
  127. void ab_tree::exchange_leaves(ab_tree_node* v, ab_tree_node* w)
  128. { // exchange leaves v and w
  129.  
  130.   GenPtr k1 = v->k[1]; 
  131.   int p1 = v->index;
  132.   ab_tree_node* u1 = v->same[1];
  133.   ab_tree_node* f1 = v->father;
  134.  
  135.   GenPtr k2 = w->k[1]; 
  136.   int p2 = w->index;
  137.   ab_tree_node* u2 = w->same[1];
  138.   ab_tree_node* f2 = w->father;
  139.  
  140.  
  141.   f1->son[p1] = w;
  142.   w->index    = p1;
  143.   w->same[1]  = u1;
  144.   w->father   = f1;
  145.  
  146.   f2->son[p2] = v;
  147.   v->index    = p2;
  148.   v->same[1]  = u2;
  149.   v->father   = f2;
  150.  
  151.   ab_tree_node* pred1 = v->son[1];
  152.   ab_tree_node* succ1 = v->son[2];
  153.  
  154.   ab_tree_node* pred2 = w->son[1];
  155.   ab_tree_node* succ2 = w->son[2];
  156.  
  157.   w->son[1] = pred1;
  158.   if (pred1) pred1->son[2] = w;
  159.   if (succ1!=w) 
  160.   { w->son[2] = succ1;
  161.     succ1->son[1] = w;
  162.    }
  163.  
  164.   if (pred2==v) pred2 = w;
  165.  
  166.  
  167.   v->son[1] = pred2;
  168.   v->son[2] = succ2;
  169.   pred2->son[2] = v;
  170.   if (succ2) succ2->son[1] = v;
  171.  
  172.   // minimum & maximum:
  173.   if (v==minimum) minimum = w;
  174.   if (w==maximum) maximum = v;
  175.  
  176.   // overwrite inner copies:
  177.   
  178.   int pos1=1;
  179.   while(u1->same[pos1]!=v) pos1++;
  180.  
  181.   int pos2=1;
  182.   if (u2) while(u2->same[pos2]!=w) pos2++;
  183.  
  184.   u1->k[pos1] = k2;
  185.   u1->same[pos1] = w;
  186.  
  187.   if (u2) 
  188.   { u2->k[pos2] = k1;
  189.     u2->same[pos2] = v;
  190.    }
  191.  
  192. }
  193.  
  194. void ab_tree::reverse_items(ab_tree_node* v, ab_tree_node* w)
  195. { // reverse sequence of leaves: v, ..., w
  196.  
  197.   if (v==w) return;
  198.  
  199. /*
  200.   if (cmp(v->k[1],w->k[1])<0) 
  201.   { newline;
  202.     cout << "a = "; print_key(v->k[1]); newline;
  203.     cout << "b = "; print_key(w->k[1]); newline;
  204.     error_handler(1,"ab_tree: illegal reverse_items(a,b)\n");
  205.    }
  206. */
  207.  
  208.   ab_tree_node* u;
  209.  
  210.   for(;;)
  211.   { exchange_leaves(v,w);
  212.     u = pred(v);
  213.     if (u == w) break;
  214.     v = succ(w);
  215.     if (v==u) break;
  216.     w = u;
  217.    }
  218.  
  219. }
  220.  
  221.  
  222.  void ab_tree::clear()
  223.  { if (root!=0) del_tree(root);
  224.    maximum=minimum=root=0;
  225.    count = 0;
  226.    height=-1;
  227.   }
  228.  
  229.  
  230.  void ab_tree::del(GenPtr key)
  231.  { if (!root) return;                      // s.n.
  232.  
  233.    ab_tree_node* w=locate(key);
  234.  
  235.    if(w && cmp(w->k[1],key) == 0)  del_item(w);
  236.  
  237.    else /* error_handler(1,"ab_tree: del(key):key is not in tree") */;
  238.  }
  239.  
  240.  
  241. ab_tree_node* ab_tree::expand(ab_tree_node* v,int i)
  242.  
  243. // expand v by returning an additional son to the right of w
  244. // --> w is the i-th son of v
  245. // s.n.: if i==0 then  new leftmost son
  246. // expand does not test a<=number of sons(v)<=b
  247. // m.w. expand does not set same links for new leaves
  248.  
  249.  {
  250.    // move the nodes right to w to give an additional son to 
  251.    // the right of w
  252.  
  253.    int l=(v->p);
  254.  
  255.    if (i < l)
  256.    {
  257.      v->son[l+1]=v->son[l];
  258.      v->son[l+1]->index=l+1;
  259.      l--;
  260.     }
  261.  
  262.    while(i < l) 
  263.    { 
  264.      v->k[l+1] = v->k[l];
  265.      v->same[l+1] = v->same[l];
  266.  
  267.      v->son[l+1]=v->son[l];
  268.      v->son[l+1]->index=l+1;
  269.  
  270.      l--;
  271.     };
  272.  
  273.    if (v->height>1)
  274.       v->son[i+1] = new ab_tree_node(0,v->height-1,i+1,v,b);
  275.    else  
  276.       v->son[i+1] = new ab_tree_node(0,v->height-1,i+1,v,1);
  277.  
  278.    (v->p)++;
  279.  
  280.    return v->son[i+1];
  281. }                     
  282.                      
  283.  
  284. void ab_tree::split_node(ab_tree_node* v)
  285. {
  286.  /* adding a child increases the degree of v by 1. If v->p<=b after
  287.     adding the new leave, then we are done . Otherwise we have to 
  288.     split v. Splitting can propagate ==> Loop 
  289.  
  290.     m.w. changes same links between nodes                          */
  291.  
  292.   ab_tree_node* y;
  293.  
  294.   while (v->p==b+1) 
  295.   {
  296.     if (v!=root)  y = v->father;
  297.     else 
  298.     { y=new ab_tree_node(1,v->height+1,0,0,b);
  299.       root=y;height++;
  300.       y->son[1]=v;
  301.       v->index=1;
  302.       v->father=y;
  303.      };
  304.  
  305.  
  306.     register ab_tree_node* u;
  307.  
  308.     u = expand(y,v->index);   // u <-- new right brother of v
  309.  
  310.     int down =(int)((b+1)/2) ;
  311.     int up = (b+1)- down;
  312.  
  313.  
  314.     if (u->index <= b)
  315.     { y->k[u->index] = y->k[v->index];
  316.       y->same[u->index] = y->same[v->index];
  317.      }
  318.  
  319.     y->k[v->index] = v->k[down];
  320.     y->same[v->index]  = v->same[down];
  321.     y->same[v->index]->same[1] = y;    
  322.  
  323.  
  324.     // split v, i.e. take the rightmost (b+1)/2 children and keys
  325.     // away from v and incorporate them into u and store key v->k[(b+1)/2]
  326.     // in y ( = father(v))  between the pointers to v and u i.e. at position
  327.     // v->index
  328.  
  329.     // m.w. change same links of v to y and u
  330.  
  331.     register int j;
  332.  
  333.     for (j=1;j<up;j++)    
  334.     {
  335.       u->son[j] = v->son[down+j];
  336.       u->son[j]->index=j;
  337.       u->son[j]->father=u;
  338.       u->k[j] = v->k[down+j];
  339.       u->same[j] = v->same[down+j]; 
  340.       u->same[j]->same[1] = u;      
  341.  
  342.       v->son[down+j] = 0;      // muss das sein ?
  343.       v->same[down+j] = 0;          
  344.       v->k[down+j] = 0;
  345.  
  346.      };
  347.  
  348.     u->son[up]=v->son[b+1];
  349.     u->son[up]->index=up;
  350.     u->son[up]->father=u;
  351.  
  352.     v->son[b+1] = 0;          // und das?
  353.     v->same[down] = 0;                 
  354.     v->k[down] = 0;
  355.  
  356.     v->p = down;             // change number of children
  357.     u->p = up;
  358.  
  359.     v = y;
  360.   }
  361.  
  362. };
  363.  
  364. ab_tree_node* ab_tree::insert(GenPtr key, GenPtr inf)
  365. {
  366.  
  367.  if (root==0) { root=new ab_tree_node(0,0,0,0,1);
  368.                 copy_key(key);
  369.                 copy_inf(inf);
  370.                 root->inf = inf;
  371.                 root->k[1]= key;
  372.                 height=0;
  373.                 maximum=minimum=root;
  374.                 count++;
  375.                 return root;
  376.                }
  377.  
  378.  // insert_at_item calls copy_key & copy_inf
  379.  
  380.  ab_tree_node* p = locate(key);
  381.  if (p==nil) p = maximum;
  382.  return insert_at_item(p,key,inf);
  383.  
  384. };
  385.  
  386. ab_tree_node* ab_tree::insert_at_item(ab_tree_node* w, GenPtr key, GenPtr inf)
  387. { 
  388.   // insert a new item (key,inf) left or right of leaf w  (according to key(w))
  389.  
  390.    copy_inf(inf);
  391.  
  392.    ab_tree_node* v;
  393.  
  394.     if (cmp(w->k[1],key)!=0)
  395.     {
  396.       copy_key(key);
  397.  
  398.      if ( w!=minimum && cmp(w->son[1]->k[1],key) > 0)
  399.       { cout << "INSERT_AT: WRONG POSITION\n";
  400.         cout << "insert:   key = "; print_key(key); cout << "\n";
  401.         if (w!=maximum) 
  402.            cout << "succ-pos: key = "; print_key(w->son[2]->k[1]); cout << "\n";
  403.         cout << "position: key = "; print_key(w->k[1]); cout << "\n";
  404.         cout << "pred-pos: key = "; print_key(w->son[1]->k[1]); cout << "\n";
  405.         error_handler(1,"ab_tree::insert_at : wrong position "); 
  406.        }
  407.  
  408.      if ( w!=maximum && cmp(w->son[2]->k[1],key) < 0)
  409.       { cout << "INSERT_AT: WRONG POSITION\n";
  410.         cout << "insert:   key = "; print_key(key); cout << "\n";
  411.         cout << "succ-pos: key = "; print_key(w->son[2]->k[1]); cout << "\n";
  412.         cout << "position: key = "; print_key(w->k[1]); cout << "\n";
  413.         if (w!=minimum)
  414.            cout << "pred-pos: key = "; print_key(w->son[1]->k[1]); cout << "\n";
  415.         error_handler(1,"ab_tree::insert_at : wrong position "); 
  416.        }
  417.  
  418.  
  419.         count++;
  420.         if (root==w) {   v=new ab_tree_node(2,1,0,0,b);
  421.                          root=v;height=1;
  422.                          ab_tree_node* u;
  423.                          if (cmp(key,w->k[1])<0)
  424.                              {   
  425.                                  u=new ab_tree_node(0,0,1,v,1);
  426.                                  v->son[1]=u;u->k[1]=key; u->inf=inf;
  427.                                  v->son[2]=w ;
  428.                                  v->p=2;v->k[1]=u->k[1];
  429.                  u->same[1] = v;
  430.                                  v->same[1] = u;
  431.                  w->index=2;
  432.                                  minimum=u;
  433.                                  u->son[2] = w;
  434.                                  w->son[1] = u;
  435.                              }
  436.                          else {
  437.                                  u=new ab_tree_node(0,0,2,v,1);
  438.                                  v->son[1]=w;
  439.                  w->same[1] = v;
  440.                                  v->same[1] = w;
  441.                                  v->son[2]=u;u->k[1]=key; u->inf=inf;
  442.                                  v->p=2;v->k[1]=w->k[1];
  443.                                  w->index=1; 
  444.                                  maximum=u;
  445.                                  w->son[2] = u;
  446.                                  u->son[1] = w;
  447.                               }
  448.                          w->father=v;
  449.  
  450.                          return u;
  451.                       }; 
  452.  
  453.     if ((w!=maximum) && (cmp(key,w->k[1])>0)) w=w->son[2];
  454.  
  455.         ab_tree_node* u;
  456.  
  457.         int index1 = w->index;
  458.  
  459.         v = w->father;
  460.  
  461.         if (cmp(key,w->k[1])<0)
  462.         { u = expand(v,index1-1);   // new son u left of w
  463. /*
  464.                  v
  465.  
  466.               /  |  \
  467.  
  468.                 (u)  w  
  469. */
  470.           u->k[1] = key;
  471.           u->inf = inf;
  472.  
  473.           u->son[2] = w;
  474.           u->son[1] = w->son[1];
  475.           w->son[1] = u;
  476.  
  477.       u->same[1] = v;        
  478.           v->k[index1] = key;
  479.           v->same[index1] = u ;  
  480.  
  481.           if (minimum == w)  
  482.              minimum=u;
  483.           else 
  484.              u->son[1]->son[2] = u;
  485.  
  486.          }
  487.         else 
  488.         { u = expand(v,index1);   // new son u right of w
  489. /*
  490.                  v
  491.  
  492.               /  |  \
  493.  
  494.              w  (u)     
  495. */
  496.           u->k[1] = key;
  497.           u->inf = inf;
  498.  
  499.           u->son[1] = w;
  500.           u->son[2] = w->son[2];
  501.           w->son[2] = u;
  502.  
  503.           if (maximum == w)  
  504.           {
  505.             maximum=u;
  506.             v->k[index1] = w->k[1];
  507.         w->same[1] = v;        
  508.         v->same[index1] = w ;  
  509.  
  510.            }
  511.           else
  512.           {
  513.             v->k[index1+1] = key;
  514.         u->same[1] = v;        
  515.         v->same[index1+1] = u ;  
  516.  
  517.             u->son[2]->son[1] = u;
  518.            }
  519.  
  520.          }
  521.  
  522.         if (v->p > b) split_node(v);
  523.  
  524.         return u;
  525.       }
  526.    else { clear_inf(w->inf);
  527.           w->inf = inf; 
  528.           return w;
  529.          }
  530.    };
  531.  
  532. ab_tree_node* ab_tree::locate(GenPtr key) const
  533.    {
  534.   /* searching for an element key in a (a,b)-tree ;
  535.    we search down the tree starting at the root r until we reache 
  536.    a leave. In each node v we use the sequence k[1](v),..k[v->p-1](v) 
  537.    in order to guide the search to the proper subtree.In the the
  538.    function we assume that k[0](v)<key<k[v->p](v) for every
  539.    element key in U
  540.    locate returns a pointer to a leave*/ 
  541.  
  542.   register ab_tree_node* v = root;
  543.   register int i;
  544.  
  545.   if (v == nil) return nil;
  546.  
  547.    while (v->p)      /* while v is not a leave*/
  548.    { for(i=1; i < v->p && cmp(key,v->k[i]) > 0; i++);   // s.n.
  549.      v=v->son[i];
  550.     };
  551.  
  552.   return (cmp(key,v->k[1]) <= 0) ? v : nil;
  553. };
  554.  
  555. ab_tree_node* ab_tree::locate_succ(GenPtr key) const
  556. { ab_tree_node* v = locate(key);
  557.   if (v==0) return maximum;
  558.   if (cmp(key,v->k[1])==0) return v;
  559.   return v->son[1];
  560.  }
  561.  
  562. ab_tree_node* ab_tree::locate_pred(GenPtr key) const
  563. { ab_tree_node* v = locate(key);
  564.   if (v==0) return maximum;
  565.   if (cmp(key,v->k[1])==0) return v;
  566.   return v->son[1];
  567.  }
  568.  
  569.  
  570. ab_tree_node* ab_tree::lookup(GenPtr k) const 
  571. { ab_tree_node* p = locate(k);
  572.   if (p && cmp(k,key(p))!=0 ) p = 0;
  573.   return p;
  574.  }
  575.  
  576.  
  577. void ab_tree::fuse(ab_tree_node* v,ab_tree_node* y)
  578.    {
  579.    /* fuse v and y, i.e. make all sons of y to sons of v and move all
  580.       keys from y to v and delete node y; also move one key (the key
  581.       between the pointers to y and v) from z to v; (note that this will
  582.       shrink z, i.e. decrease the arity of z by one)  
  583.    */
  584.  
  585.    ab_tree_node* z=v->father;
  586.  
  587.    GenPtr hilf=z->k[v->index] ;     /* before k[v->p] was not used {=0}*/
  588.               /* 
  589.                  we only must copy the pointer of son and the node-keys
  590.                  from y to v
  591.               */
  592.           /* change same-pointer of y and z                     */
  593.    v->k[v->p]=hilf; 
  594.    v->same[v->p]=z->same[v->index];  
  595.    v->same[v->p]->same[1] = v;       
  596.  
  597.    for(int i=1;i<y->p;i++) {  v->k[v->p+i]=y->k[i];
  598.                   v->same[v->p+i]=y->same[i];    
  599.                   v->same[v->p+i]->same[1]=v;    
  600.                               v->son[v->p+i]=y->son[i];
  601.                               v->son[v->p+i]->index=v->p+i;
  602.                               v->son[v->p+i]->father=v;
  603.                            };
  604.    v->son[v->p+y->p]=y->son[y->p];   /* copy of the last son from y*/
  605.    v->son[v->p+y->p]->index=v->p+y->p;
  606.    v->son[v->p+y->p]->father=v;
  607.  
  608.    v->p=v->p+y->p;
  609.  
  610.    for(i=v->index;i<z->p;i++) { z->k[i]=z->k[i+1];
  611.                 z->same[i] = z->same[i+1]; 
  612.                                 z->son[i+1]=z->son[i+2];
  613.                                 if (z->son[i+1]!=0){z->son[i+1]->index=i+1; 
  614.                                 z->son[i+1]->father=z;};
  615.                                };
  616.    z->p--;
  617.    z->k[z->p]=0;      
  618.    z->same[z->p]=0;   
  619.  
  620.    delete y;
  621.    
  622.   };
  623.  
  624.  
  625.  void ab_tree::share(ab_tree_node* v,ab_tree_node* y,int direct)
  626.  {
  627.   /* we assume that y is the right brother of v;
  628.      take the leftmost son away from y and make it an additional(right-
  629.      most) son of v; also move one key( the key between the pointers
  630.      to v and y) from z down to v and replace it by the leftmost
  631.      key of y;    
  632.      the other case is equivalent
  633.      let z be the father of v
  634.    */
  635.  
  636.      ab_tree_node* z=v->father;
  637.  
  638.      if (direct==1)  { 
  639.                        v->son[v->p+1]=y->son[1];
  640.                        v->son[v->p+1]->index=v->p+1;
  641.                        v->son[v->p+1]->father=v;
  642.                        v->k[v->p]=z->k[v->index];
  643.                v->same[v->p]=z->same[v->index];   
  644.                        v->same[v->p]->same[1] = v;    
  645.                        z->k[v->index]=y->k[1];
  646.                        z->same[v->index]=y->same[1];      
  647.                z->same[v->index]->same[1]=z;      
  648.  
  649.                        v->p++;    
  650.  
  651.                        for(int i=1;i<(y->p)-1;i++) 
  652.                        { y->son[i]=y->son[i+1];
  653.                          y->son[i]->index=i;
  654.                          y->k[i]=y->k[i+1];
  655.                          y->same[i]=y->same[i+1];
  656.                        };
  657.  
  658.                        y->p--;     // decrease number of children
  659.  
  660.                        y->son[y->p]=y->son[y->p+1];
  661.                        y->son[y->p]->index=y->p;
  662.                        y->son[y->p+1]=0;  
  663.                        y->k[y->p]=0;
  664.                y->same[y->p] = 0;                 
  665.                      }
  666.      else            {    // y is at the left side of v
  667.                        for(int i=v->p;i>=1;i--) 
  668.                        { v->son[i+1]=v->son[i];
  669.                          v->son[i+1]->index=i+1;
  670.                          v->k[i+1]=v->k[i];
  671.                          v->same[i+1]=v->same[i]; 
  672.                         };
  673.  
  674.                        v->son[1]=y->son[y->p];
  675.                        v->son[1]->index=1;
  676.                        v->son[1]->father=v;
  677.                        y->son[y->p]=0;
  678.  
  679.                        v->p++;
  680.                        y->p--;
  681.  
  682.                        v->k[1]=z->k[y->index];
  683.                v->same[1]=z->same[y->index];     
  684.                v->same[1]->same[1] = v;            
  685.                        z->k[y->index]=y->k[y->p];
  686.                        z->same[y->index]=y->same[y->p];  
  687.                        z->same[y->index]->same[1] = z;   
  688.                        y->k[y->p]=0;
  689.                y->same[y->p]=0;                    
  690.                      };
  691.      }
  692.  
  693.  
  694.  void ab_tree::del_item(ab_tree_node* w)
  695.     {
  696.          /* 
  697.           we must delete leave w with father v
  698.           we shrink v by deleting leave w and one of the keys in the 
  699.           adjacent to the pointer to w 
  700.           (if w is the i-th son of v then we delete k[i](v) if i<v->p
  701.           k[i-1](v) if i=v->p  ).
  702.       m.w. if i=v->p we overwrite the inner node 
  703.            in which key w->k[1] is stored with k[i-1](v)
  704.            and then delete k[i-1](v)
  705.          */
  706.  
  707.  
  708.        if (w==nil) error_handler(1,"ab_tree: nil item in del_item");
  709.  
  710.        count--;
  711.  
  712.        if (maximum==minimum)  
  713.         { maximum=minimum=root=0; 
  714.           height=-1; 
  715.           clear_key(w->k[1]);
  716.           clear_inf(w->inf);
  717.           delete w; 
  718.           return;
  719.          }
  720.             /* here w==root==> last leave will be deleted*/
  721.        
  722.        ab_tree_node* succ = w->son[2];
  723.        ab_tree_node* pred = w->son[1];
  724.  
  725.        if (pred) pred->son[2]   = succ;
  726.        else minimum = succ;
  727.        if (succ) succ->son[1] = pred;
  728.        else  maximum = pred;
  729.  
  730.  
  731.        ab_tree_node* v    = w->father;
  732.  
  733.        v->son[w->index]=0;
  734.        if (w->index==v->p) {
  735.                  if (succ)
  736.                  { //overwrite copies in inner node u
  737.                    ab_tree_node* u = w->same[1];
  738.                    int pos=1;
  739.                                while(u->same[pos]!=w) pos++;
  740.                    u->k[pos]=pred->k[1];  
  741.                    u->same[pos]=pred;
  742.                    pred->same[1] = u;
  743.                  }
  744.                  else
  745.                    v->same[v->p-1]->same[1]=0; 
  746.                              v->k[v->p-1]=0;
  747.                  v->same[v->p-1]=0;           
  748.                }
  749.        else                { v->k[w->index]=0 ;
  750.                  v->same[w->index]=0;         
  751.                              for(int i=w->index;i<(v->p)-1;i++)
  752.                              { v->k[i]=v->k[i+1];
  753.                                v->same[i]=v->same[i+1]; 
  754.                                v->son[i]=v->son[i+1];
  755.                                v->son[i]->father=v;
  756.                                v->son[i]->index=i;
  757.                               };
  758.                              v->son[v->p-1]=v->son[v->p];
  759.                              v->son[v->p]=0;
  760.                              v->k[v->p-1]=0;
  761.                              v->same[v->p-1]=0;          
  762.                              v->son[v->p-1]->father=v;
  763.                              v->son[v->p-1]->index=v->p-1;
  764.                            };
  765.  
  766.        clear_key(w->k[1]);
  767.        clear_inf(w->inf);
  768.        delete w;
  769.  
  770.        (v->p)--;
  771.        
  772.        if ((v==root) && (v->p==1)) {  
  773.                                   if (v->son[1]==0) 
  774.                                       {v->son[1]=v->son[2];
  775.                                        v->son[2]=0;  };
  776.                                   root=v->son[1];
  777.                                   delete v;
  778.                                   root->index=0;
  779.                                   root->father=0;
  780.                                   root->p=0;
  781.                                   root->height=0;
  782.                                   height=0;
  783.                                   minimum=maximum=root;
  784.                                   return; 
  785.                                 };
  786.  
  787.        if (v->p >= a) return;
  788.  
  789.     /* otherwise v needs to be rebalanced by either fusing or sharing
  790.      let y be any brother of v*/
  791.      ab_tree_node* z;
  792.      ab_tree_node* y;
  793.      int dir;
  794.        if (v->index==1)  {
  795.                             z=v->father;
  796.                             y=z->son[v->index+1] ;
  797.                            dir=1;    //  y is the right son of v
  798.                          }
  799.        else              { 
  800.                             z=v->father;
  801.                             y=z->son[v->index-1] ;
  802.                            dir =0;   //  y is the left son of v
  803.                          };
  804.        while ((v->p==a-1) && (y->p==a))
  805.             {
  806.              if (dir==1) fuse(v,y); 
  807.              else  fuse(y,v); 
  808.  
  809.              if (z==root) {
  810.                            if (z->p==1) {
  811.                                          if (dir==1){
  812.                                                       root=v;
  813.                                                       v->father=0;
  814.                                                       v->index=0;   }
  815.                                          else {
  816.                                                 root=y;
  817.                                                 y->father=0;
  818.                                                 y->index=0;    };
  819.                                          height--;
  820.                                          delete z;  
  821.                                        };
  822.                            return;
  823.                           };
  824.              v=z;       // continue recursion
  825.              if (v->index==1)  {z=v->father;
  826.                                 y=z->son[v->index+1] ;
  827.                                 dir=1;  // y is the right son of v
  828.                                }
  829.              else              { z=v->father;
  830.                                  y=z->son[v->index-1];
  831.                                  dir=0;
  832.                                };
  833.             };
  834.     /* we have either v->p>=a and rebalancing is completed or
  835.      v->p = a-1 and y->p > a and rebalancing is completed by sharing;*/
  836.  
  837.       if (v->p==a-1)
  838.         {       /*
  839.                  it is important to which side y is in order to v
  840.                  ==> dir is an information about in the function share
  841.                 */
  842.            share(v,y,dir);
  843.         };
  844.       return;
  845.  }
  846.  
  847.  
  848. ab_tree& ab_tree::conc(ab_tree& s2)
  849.  
  850. { 
  851.   if ((a!=s2.a)||(b!=s2.b)) 
  852.      error_handler(1,"ab_tree: incompatible trees in concatenate operation");
  853.  
  854.   if (s2.root==0) return *this;
  855.  
  856.   if (root==0) 
  857.   { root=s2.root;
  858.     maximum=s2.maximum;
  859.     minimum=s2.minimum;
  860.     height=s2.height;
  861.     count =s2.count;
  862.    }
  863.   else
  864.   { if (cmp(maximum->k[1],s2.minimum->k[1])>=0) 
  865.                     error_handler(1,"ab_tree: join(S,T) : max(S)>=min(T)"); 
  866.  
  867.     concat(*this,s2,maximum,maximum->k[1]);
  868.  
  869.     // link leaves 
  870.     maximum->son[2]=s2.minimum;       
  871.     s2.minimum->son[1]=maximum;
  872.  
  873.     maximum=s2.maximum;              
  874.    }
  875.  
  876.   s2.root=0;
  877.   s2.maximum=0;
  878.   s2.minimum=0;
  879.   s2.height=-1;
  880.  
  881.   return *this;
  882. }
  883.  
  884.  
  885. /*---------------------------------------------------------------------
  886.   global functions
  887. ----------------------------------------------------------------------*/
  888.  
  889. void concat(ab_tree& s1,ab_tree& s2,ab_tree_node* current,GenPtr cur_key)
  890. { 
  891.   // Result in s1
  892.  
  893.   ab_tree_node* v=s1.root;
  894.   ab_tree_node* w=s2.root;
  895.   int h1=v->height;     
  896.   int h2=w->height;
  897.   int i;
  898.  
  899.   if(h1==h2)
  900.      { ab_tree_node* z=new ab_tree_node(2,h1+1,0,0,s1.b);
  901.        z->son[1]=v;z->son[2]=w; z->k[1]=cur_key;
  902.        z->son[1]->father=z; z->son[2]->father=z;
  903.        z->son[1]->index=1;z->son[2]->index=2;
  904.        z->same[1]=current;              
  905.        current->same[1]=z;              
  906.        s1.height++;
  907.        s1.root=z;
  908.     }
  909.   else { if (h1>h2)
  910.          {
  911.             for(i=1;i<h1-h2;i++,v=v->son[v->p]);  
  912.             v->son[v->p+1]=w;
  913.             v->son[v->p+1]->father=v;
  914.             v->son[v->p+1]->index=v->p+1;
  915.             v->k[v->p]=cur_key;
  916.         v->same[v->p]=current;     
  917.         current->same[1]=v;        
  918.          v->p++;
  919.         if (v->p==s1.b+1)  {s1.split_node(v);  };
  920.         }
  921.         else /* h1<h2 */
  922.         {
  923.        for(i=1;i<=h2-h1-1;i++,w=w->son[1]);
  924.            for(i=w->p;i>1;i--)
  925.             { w->son[i+1]=w->son[i];
  926.               w->son[i+1]->father=w;
  927.             w->son[i+1]->index=i+1;
  928.               w->k[i]=w->k[i-1];
  929.           w->same[i]=w->same[i-1];   
  930.             };
  931.            w->p++;
  932.            w->son[2]=w->son[1];
  933.            w->son[2]->father=w;
  934.            w->son[2]->index=2;
  935.            w->son[1]=v;
  936.            w->son[1]->father=w;
  937.            w->son[1]->index=1;
  938.            w->k[1]=cur_key;
  939.        w->same[1]=current;             
  940.        current->same[1]=w;             
  941.            if (w->p==s2.b+1) {s2.split_node(w);};
  942.        s1.root =  s2.root;
  943.        s1.height =  s2.height;
  944.         }
  945.       }
  946.  
  947.   /* maximum/minimum are now undefined  */
  948.  
  949. }
  950.  
  951.  
  952.  
  953. /*
  954. void ab_tree::split_at_key(GenPtr y,ab_tree& L,ab_tree& R)
  955. { ab_tree_node* w = locate(y);
  956.   if (!w) error_handler(1,"ab_tree: split: no item ");
  957.   split_at_item(w,L,R);
  958.  }
  959. */
  960.  
  961. void ab_tree::split_at_item(ab_tree_node* w,ab_tree& L,ab_tree& R)
  962.   {
  963.     if(((a!=L.a)||(a!=R.a))||((b!=L.b)||(b!=R.b)))
  964.        error_handler(1,"ab_tree: incompatible trees in split operation");
  965.     
  966.     /* initialisation   */
  967.     L.root=L.minimum=L.maximum=0;L.height=-1;
  968.     R.root=R.minimum=R.maximum=0;R.height=-1;
  969.  
  970.     if(root==0) return;
  971.  
  972.     if (w==0) 
  973.     { R.root = root;
  974.       R.height = height;
  975.       R.maximum = maximum;
  976.       R.minimum = minimum;
  977.       R.count = count;
  978.       root = 0;
  979.       height = -1;
  980.       maximum = 0;
  981.       minimum = 0;
  982.       count = 0;
  983.       return;
  984.      }
  985.  
  986.     if (w==maximum) 
  987.     { L.root = root;
  988.       L.height = height;
  989.       L.maximum = maximum;
  990.       L.minimum = minimum;
  991.       L.count = count;
  992.       root = 0;
  993.       height = -1;
  994.       maximum = 0;
  995.       minimum = 0;
  996.       count = 0;
  997.       return;
  998.      }
  999.  
  1000.     ab_tree_node* l;
  1001.     ab_tree_node* r;    // pointers to the roots of the left and right subtree
  1002.  
  1003.  
  1004.     /* parameters for concat  */
  1005.  
  1006.     ab_tree_node* current_l=0 ;
  1007.     GenPtr           current_l_key=0;
  1008.  
  1009.     ab_tree_node* current_r=0;  
  1010.     GenPtr           current_r_key=0;
  1011.  
  1012.     int i;
  1013.  
  1014.  
  1015.     /* w is a pointer to the leave y  */
  1016.     ab_tree_node* v;
  1017.  
  1018.     /* store leaf to split at         */
  1019.     ab_tree_node* leaf=w;
  1020.  
  1021.  
  1022.      l = w;
  1023.      r = 0;
  1024.  
  1025.       do{
  1026.          v=w->father;
  1027.          int index_of_w = w->index; 
  1028.  
  1029.        /* now we have construct the  left and right subtrees and the pointers
  1030.           to the roots  --> we must construct two trees with these roots*/
  1031.  
  1032.         if ((L.root==0)&&(l!=0))  { L.root=l;
  1033.                         L.height=l->height; 
  1034.                         L.root->father=0;
  1035.                         L.root->index=0;
  1036.                       }
  1037.         else { if ((L.root!=0)&&(l!=0))
  1038.                  {  ab_tree L1(L.a,L.b);
  1039.                 L1.root=l;
  1040.                     L1.height=l->height;
  1041.                     L1.root->father=0;
  1042.                     L1.root->index=0;
  1043.                 concat(L1,L,current_l,current_l_key);
  1044.                 L.root  = L1.root;
  1045.                     L.height= L1.height;
  1046.                     L.count = L1.count;
  1047.  
  1048.                     L1.root=0;
  1049.              }
  1050.              }
  1051.        if ((R.root==0)&&(r!=0))  {R.root=r;
  1052.                       R.height=r->height;
  1053.                       R.root->father=0;
  1054.                       R.root->index=0;
  1055.                                   R.root->p=r->p;
  1056.                      }
  1057.        else { if ((R.root!=0)&&(r!=0))
  1058.                 { ab_tree R1(R.a,R.b);
  1059.             R1.root=r;
  1060.           R1.height=r->height;
  1061.                   R1.root->father=0;
  1062.                   R1.root->index=0;
  1063.                   R1.root->p=r->p;
  1064.           concat(R,R1,current_r,current_r_key);
  1065.                   R1.root=0;
  1066.             }
  1067.             }
  1068.         if (v!=0)
  1069.         {
  1070.          if (index_of_w==1)     /* w is leftmost son of v */
  1071.          { l=0;
  1072.            r=v;
  1073.            current_r=v->same[1];
  1074.            current_r_key=v->k[1];
  1075.        r->same[1]->same[1]=0;        
  1076.        for(i=2;i<r->p;i++) 
  1077.             {  r->son[i-1]=r->son[i];
  1078.               r->son[i-1]->index=i-1;
  1079.             r->k[i-1]=r->k[i];
  1080.            r->same[i-1]=r->same[i];  
  1081.             }
  1082.            r->son[r->p-1]=r->son[r->p];    /* last son */
  1083.            r->son[r->p-1]->index=r->p-1;
  1084.            r->son[r->p]=0;
  1085.            r->p--; 
  1086.            r->k[r->p]=0;
  1087.        r->same[r->p]=0;      
  1088.            if (r->p==1) r=r->son[1];
  1089.          } 
  1090.          else {if ( index_of_w==v->p )
  1091.                  {  r=0;
  1092.                     l=v;
  1093.             l->son[l->p]=0;  /* last son */
  1094.             l->p--;
  1095.             current_l=l->same[index_of_w-1];
  1096.             current_l_key=current_l->k[1];
  1097.                     l->k[l->p]=0;
  1098.             l->same[l->p]->same[1]=0;   
  1099.             l->same[l->p]=0;            
  1100.                     if (l->p==1) l=l->son[1];
  1101.         } 
  1102.                else  /* if w is not the leftmost or rightmost son of v*/
  1103.                {  
  1104.                  r=v;
  1105.                  l=new ab_tree_node(index_of_w-1,v->height,0,0,R.b);
  1106.           current_l=v->same[index_of_w-1];
  1107.           current_l_key=current_l->k[1];
  1108.          current_r=v->same[index_of_w];   
  1109.          current_r_key=current_r->k[1];
  1110.          // current_r=(v->k[index_of_w])-1;   ERROR: liefert neuen Schluessel ;
  1111.                  for(i=1;i<index_of_w-1;i++)
  1112.              {
  1113.            l->son[i]=v->son[i];
  1114.            l->son[i]->index=i;
  1115.                    l->son[i]->father=l;
  1116.            l->k[i]=v->k[i];
  1117.            l->same[i]=v->same[i];  
  1118.            l->same[i]->same[1]=l;  
  1119.           };
  1120.          l->son[index_of_w-1]=v->son[index_of_w-1];
  1121.          l->son[index_of_w-1]->index=index_of_w-1;
  1122.                  l->son[index_of_w-1]->father=l;
  1123.  
  1124.                  r->son[index_of_w] = 0;   // changed
  1125.  
  1126.              for (i=1;i<r->p-index_of_w;i++)
  1127.           {
  1128.            r->son[i]=r->son[i+index_of_w];
  1129.                    r->son[i+index_of_w]=0;
  1130.                     r->son[i]->index=i;
  1131.                    r->son[i]->father=r;
  1132.            r->k[i]=r->k[i+index_of_w];
  1133.            r->same[i]=r->same[i+index_of_w]; 
  1134.                    r->k[i+index_of_w]=0;
  1135.            r->same[i+index_of_w]=0;
  1136.           };
  1137.              r->son[r->p-index_of_w]=r->son[r->p];  /* last son */
  1138.                  r->son[r->p]=0;
  1139.          r->son[r->p-index_of_w]->index=i;
  1140.                  r->son[r->p-index_of_w]->father=r;
  1141.          r->p=r->p-index_of_w;
  1142.                  if (l->p==1) l=l->son[1];
  1143.                  if (r->p==1) r=r->son[1];
  1144.                 };
  1145.                };
  1146.               };
  1147.  
  1148.  /* initialisation for the next iteration  */
  1149.   w=v;
  1150.  }
  1151.  while (w!=0);
  1152.  
  1153.  
  1154.  /* unlink leaves    m.w.         */
  1155.  leaf->same[1]=0;
  1156.  leaf->son[2]->son[1]=0;
  1157.  leaf->son[2]=0;
  1158.  
  1159.  /* redefine maximum and minimum  */
  1160.  L.minimum=minimum;
  1161.  ab_tree_node* help=L.root;
  1162.  while (help->p) help=help->son[help->p];
  1163.  L.maximum=help;
  1164.  help=R.root;
  1165.  while (help->son[1]!=0) help=help->son[1];
  1166.  R.minimum=help;
  1167.  R.maximum=maximum;
  1168.  
  1169.  maximum=minimum=root=l=r=0;
  1170.  height=-1; 
  1171.  count = 0;
  1172.  
  1173.  delete l;
  1174.  delete r;
  1175.  
  1176. }
  1177.  
  1178. void ab_tree::pr_ab_tree(ab_tree_node* localroot,int blancs) const
  1179.  
  1180. { 
  1181.   if (localroot==0)
  1182.    { for(int j=1;j<=blancs;j++) cout<<" ";
  1183.      cout << "NIL\n";
  1184.      return;
  1185.     }
  1186.   
  1187.   if (localroot->p == 0) 
  1188.    { for(int j=1;j<=blancs;j++) cout<<" ";
  1189.      print_key(localroot->k[1]); 
  1190. /*
  1191.      ab_tree_node* s= localroot->same[1];
  1192.      cout << " same = "; 
  1193.      if (s) print_key(s->k[1]); 
  1194.      else cout << "NIL";
  1195. */
  1196.      cout << "\n";
  1197.     }
  1198.  
  1199.    else
  1200.     { for(int i=1;i<localroot->p;i++)
  1201.       { pr_ab_tree(localroot->son[i],blancs+10);
  1202.         for(int j=1;j<=blancs;j++) cout<<" ";
  1203.         print_key(localroot->k[i]); 
  1204. /*
  1205.         cout << " same = "; 
  1206.         print_key(localroot->same[i]->k[1]); 
  1207. */
  1208.         cout << "\n";
  1209.        };
  1210.       pr_ab_tree(localroot->son[localroot->p],blancs+10);
  1211.     }
  1212. } 
  1213.  
  1214. ab_tree_node* ab_tree::copy_ab_tree(ab_tree_node* localroot,
  1215.                                     abnode& last_leaf,int b) const
  1216. { 
  1217.   ab_tree_node* r;
  1218.  
  1219.   if (localroot->p == 0)   //leaf
  1220.    { r=new ab_tree_node(localroot->p,localroot->height,localroot->index,0,1); 
  1221.  
  1222.      r->k[1]= localroot->k[1];
  1223.      r->inf = localroot->inf;
  1224.  
  1225.      copy_key(r->k[1]);
  1226.      copy_inf(localroot->inf);
  1227.  
  1228.      r->son[1]=last_leaf;
  1229.      if (last_leaf) last_leaf->son[2] = r;
  1230.      last_leaf = r;               
  1231.  
  1232.     }
  1233.   else
  1234.    { r=new ab_tree_node(localroot->p,localroot->height,localroot->index,0,b); 
  1235.  
  1236.      for(int i=1;i<localroot->p;i++)
  1237.      { r->son[i]=copy_ab_tree(localroot->son[i],last_leaf,b);
  1238.        r->son[i]->father=r;
  1239.        r->k[i]=localroot->k[i];
  1240.        last_leaf->same[1]=r;        
  1241.        r->same[i]=last_leaf;        
  1242.       }
  1243.  
  1244.      r->son[localroot->p]=copy_ab_tree(localroot->son[localroot->p],last_leaf,b);
  1245.      r->son[localroot->p]->father=r;
  1246.    }
  1247.  
  1248.   return r;
  1249. }
  1250.         
  1251. void ab_tree::del_tree(ab_tree_node* localroot)
  1252. { // deletes subtree  rooted at localroot
  1253.  
  1254.   int k = localroot->p;
  1255.  
  1256.   for(int i=1;i<=k;i++) del_tree(localroot->son[i]);
  1257.  
  1258.   if (k==0) //leaf
  1259.   { clear_key(localroot->k[1]);
  1260.     clear_inf(localroot->inf);
  1261.    }
  1262.  
  1263.   delete localroot;
  1264. }
  1265.  
  1266. void ab_tree::change_inf(ab_tree_node* p, GenPtr x) 
  1267. { clear_inf(p->inf);
  1268.   copy_inf(x);
  1269.   p->inf = x;
  1270.  }
  1271.  
  1272.